from PriorityQueueBase import PriorityQueueBase
from PositionalList import PositionalList


class SortedPriorityQueue(PriorityQueueBase):
    """未排序的优先级队列"""

    def __init__(self):
        self._data = PositionalList()

    def __len__(self):
        return len(self._data)

    def add(self, key, value):
        new = self._Item(key, value)
        current = self._data.last()
        while current and new < current.element():
            current = self._data.before(current)
        if not current:
            self._data.add_first(new)
        else:
            self._data.add_after(current, new)

    def min(self):
        if self.is_empty():
            raise Exception('队列为空')
        p = self._data.first()
        item = p.element()
        return (item._key, item._value)

    def remove_min(self):
        if self.is_empty():
            raise Exception('队列为空')
        item = self._data.delete(self._data.first())
        return (item._key, item._value)
